A Real Application

The City of Berlin

Q: How to draw the map of the city from a noisy point-cloud of GPS locations?

A Reconstruction of Berlin

Source: mapconstruction.org

Reconstruction Goals

  • Goal: Infer the topology of XX from SS.

    • Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of XX

    • construct a topological space X̂\widehat{X} from SS to retain the topology of XX in some appropriate sense

      • homotopy equivalent
      • homeomorphic
      • geometrically close (in Hausdorff distance)

My Motivation

  • Provide a window of scales for the Vietoris–Rips complexes for a topologically-faithful reconstruction
  • Design provable reconstruction algorithms particularly for bad shapes
  • Topological perspective on Manifold and graph hypotheses for random data
    • Geometric Whitney’s Theorem by Fefferman et al.
  • Understand the topology of ℛβ(X)\mathcal{R}_\beta(X) and their shadow
  • When is the homology of ℛβ(X)\mathcal{R}_\beta(X) (and their shadow) finitely generated?

The Vietoris–Rips Complexes

  • a metric space (X,dX)(X,d_X)

  • a scale β>0\beta>0

  • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex

    • XX is the vertex set
    • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter less than β\beta is a kk-simplex.

Metric Graph Reconstruction [J. Appl. & Comp. Top., Majhi (2023)]

Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G.

Challenges

  • Bad shapes are ubiquitous in applications
    • manifolds with boundary or not a topological manifold
    • stratefied manifolds
    • Euclidean subsets with vanishing reach (due to corners)
  • A single Rips complex fails to be topologically faithful, no matter the sample density

Metric Spaces of Curvature ≤κ\leq\kappa

  • Length space: A metric space with an instrinsic metric

  • Geodesically complete: a pair can be joined by a length-minimizing path

  • geodesic triangles are “slimmer” than corresponding “model triangles” in a standard space of constant curvature κ\kappa.

  • Examples:

    • Closed Riemannian manifolds
    • Submanifolds of ℝN\mathbb{R}^N
    • stratefied manifolds
    • metric graphs
    • embedded graphs in ℝN\mathbb{R}^N
    • Euclidean Polytopes

  • Quantitative Lastchev’s Theorem for CAT(κ)\mathrm{CAT}(\kappa) Spaces (Komendarczyk, Majhi, and Tran 2024)

Euclidean Subset Reconstruction

  • The sample SS comes equipped with ∥⋅∥\|\cdot\|
  • Euclidean Vietoric–Rips ℛβ(S)\mathcal{R}_\beta(S) fails almost aways for any scale β\beta
  • Remedy?

ε\varepsilon-path Metric:

  • Fix an ε>0\varepsilon>0, proportional to dH(S,X)d_H(S,X)

  • For any two sample points a,b∈Sa,b\in S, define dSε(a,b)d_S^\varepsilon(a,b) to be the shortest distance when hopping over the points of SS with a step size ≤ε\leq\varepsilon.

ε\varepsilon-path Metric on SS
  • For a dense enough sample SS of XX, dSεd^\varepsilon_S is quasi-isometric to the length metric on XX
  • Consider the Vietoris–Rips of SS under dεd_\varepsilon; call it ℛβε(S)\mathcal{R}_\beta^\varepsilon(S)

Large-scale Distortion

  • A finite sample around a corner does not see the corner
  • Global distortion: δ(X)=supa≠bdXL(a,b)∥a−b∥\delta(X)=\sup_{a\neq b}\frac{d^L_X(a,b)}{\|a-b\|}
  • Large-scale distortion: δRε(X)=supdL(a,b)≥RdXL(a,b)dXεL(a,b)\delta^\varepsilon_R(X)=\sup_{d^L(a,b)\geq R}\frac{d^L_X(a,b)}{d^L_{X^\varepsilon}(a,b)}
  • δRε(X)→1\delta^\varepsilon_R(X)\to1 as ε→0\varepsilon\to0, provided XX is a compact length space

Euclidean Subsets (Komendarczyk, Majhi, and Tran 2024)

Let XX be a geodesic subspace of ℝN\mathbb R^N. Let ξ∈(0,1)\xi\in\left(0,1\right) and β>0\beta>0 be fixed numbers. 0<ε≤β0<\varepsilon\leq\beta such that δβε(X)≤1+(ξ1+ξ)\delta^\varepsilon_{\beta}(X)\leq1+\left(\frac{\xi}{1+\xi}\right), then for any compact subset S⊂ℝNS\subset\mathbb R^N with dH(X,S)<12ξεd_H(X,S)<\frac{1}{2}\xi\varepsilon, we have ℛβε(S)≃X\mathcal{R}_\beta^\varepsilon(S)\simeq X.

Back to Gromov: Vietoris–Rips Shadow

  • Vietoris–Rips complexes are abstact, hence contain only topological information
  • Geometric reconstruction: entails constructing X̂⊂ℝN\widehat{X}\subset\mathbb R^N from samples so that X̂≃X\widehat{X}\simeq X and dH(X̂,X)d_H(\widehat{X}, X) is controlled.
  • A good candidate for X̂\widehat{X} is the shadow of a topologically-faithful Vietoris–Rips.
  • Shadow: For simplicial complex 𝒦\mathcal K with vertices from ℝN\mathbb R^N is the union of the (Euclidean) convex hulls of simpices σ∈𝒦\sigma\in\mathcal K
    • Chambers et al. (2010); Adamaszek, Frick, and Vakili (2017)

Graph Reconstruction via Shadow

Geometric Reconstruction (Komendarczyk, Majhi, and Mitra 2025)

Let G⊂ℝ2G \subset \mathbb{R}^2 a graph. Fix any ξ∈(0,1−Θ6)\xi\in\left(0,\frac{1-\Theta}{6}\right). For any positive β<min{Δ(G),ℓ(G)12}\beta<\min\left\{\Delta(G),\frac{\ell(G)}{12}\right\}, choose a positive ε≤(1−Θ)(1−Θ−6ξ)12β\varepsilon\leq\frac{(1-\Theta)(1-\Theta-6\xi)}{12}\beta such that δβε(G)≤1+2ξ1+ξ\delta^{\varepsilon}_{\beta}(G)\leq\frac{1+2\xi}{1+\xi}. If S⊂ℝ2S\subset \mathbb R^2 is compact and dH(G,S)<12ξεd_H(G,S)<\tfrac{1}{2}\xi\varepsilon, then the shadow sh(ℛβε(S))sh(\mathcal R_\beta^\varepsilon(S)) is homotopy equivalent to GG. Moreover, dH(sh(ℛβε(S)),G)<(β+12ξε)d_H(sh(\mathcal R_\beta^\varepsilon(S)),G)<\left(\beta+\frac{1}{2}\xi\varepsilon\right).

  • Θ∈(0,1)\Theta\in(0,1): depends on the angles between tangents of edges at the graph vertices
  • Δ(G)\Delta(G): Shadow radius positive number for graphs with smooth edges